package com.lzq.leetcode.hoot100;

import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;

public class s84 {

    public int largestRectangleArea(int[] heights) {

        int len = heights.length;
        int[] leftMin = new int[len];
        int[] rightMin = new int[len];

        for (int i=0; i<len; i++) {
            leftMin[i] = -1;
            rightMin[i] = len;
        }

        Deque<Integer> stack = new LinkedList<>();
        // 找到左边第一个比其小的元素的位置
        for (int i=0; i<len; i++) {
            while (!stack.isEmpty() && heights[stack.getFirst()] >= heights[i]) {
                stack.pollFirst();
            }
            if (!stack.isEmpty())   leftMin[i] = stack.getFirst();
            stack.addFirst(i);
        }
        // 找到右边第一个比其小的元素的位置
        stack = new LinkedList<>();
        for (int i=len-1; i>=0; i--) {

            while (!stack.isEmpty() && heights[stack.getFirst()] >= heights[i]) {
                stack.pollFirst();
            }
            if (!stack.isEmpty())   rightMin[i] = stack.getFirst();
            stack.addFirst(i);
        }

        System.out.println(Arrays.toString(leftMin));
        System.out.println(Arrays.toString(rightMin));
        // 求取最大值
        int max = 0;
        for (int i=0; i<len; i++) {
            int cur = ( rightMin[i] - leftMin[i] - 1 ) * heights[i];
            max = Math.max(cur, max);

        }

        return max;
    }

    public static void main(String[] args) {
        s84 s84 = new s84();
        System.out.println(s84.largestRectangleArea(new int[]{2,0,2}));
    }
}
